﻿#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    // 376. 摆动序列
    int wiggleMaxLength(vector<int>& nums)
    {
        int ret = 0, left = 0, right;
        for (int i = 0; i < nums.size() - 1; ++i)
        {
            right = nums[i + 1] - nums[i];
            if (right == 0)
                continue;
            if (left * right <= 0)
                ret++;
            left = right;
        }
        return ret + 1;
    }

    // 300. 最长递增子序列
    int lengthOfLIS(vector<int>& nums)
    {
        vector<int> v;
        v.push_back(nums[0]);
        int n = nums.size();
        for (int i = 1; i < n; ++i)
        {
            if (nums[i] > v.back())
            {
                v.push_back(nums[i]);
            }
            else
            {
                int left = 0, right = v.size() - 1;
                while (left < right)
                {
                    int mid = (left + right) / 2;
                    if (v[mid] < nums[i])
                        left = mid + 1;
                    else
                        right = mid;
                }
                v[left] = nums[i];
            }
        }
        return v.size();
    }
};

int main()
{
    /*vector<int> v{ 1,7,4,9,2,5 };
    cout << Solution().wiggleMaxLength(v) << endl;*/

    vector<int> v{ 10,9,2,5,3,7,101,18 };
    cout << Solution().lengthOfLIS(v) << endl;

    return 0;
}